package com.liufei.class04;


import java.util.List;

// 力扣链接：https://leetcode.cn/problems/sum-lists-lcci/description/
public class Code05_AddTwoNumbers {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        int length1 = getLength(l1);
        int length2 = getLength(l2);
        // 重新指向，让curL指向最大的链表
        ListNode l = length1 > length2 ? l1 : l2;
        ListNode s = l == l1 ? l2 :l1;
        // 在使用一个指针，因为我们要返回l
        ListNode curL = l;
        ListNode curS = s;
        // 保存最长链表的最后一个，因为如果最后一个数有进位，需要这个指向一个新的节点
        ListNode last = curL;
        // 3 种情况
        // 1. curL 和 curS 节点都有
        // 2. curL 节点有
        // 3. curL 和 curS 节点都没有
        int carry = 0;
        int curNum = 0;
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            // 这里很巧妙，在next之前复制，这样就能保证curL走完的时候，last指向最后一个元素
            last = curL;
            curS = curS.next;
            curL = curL.next;
        }
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        if (carry > 0) {
            last.next = new ListNode(carry);
        }
        // 注意：这里不能直接返回l1，因为我们需要返回长的哪个，这里并不知道l1和l2哪个长
        return l;
    }


    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(7, new ListNode(1, new ListNode(6)));
        ListNode l2 = new ListNode(5, new ListNode(9, new ListNode(2)));

        Code05_AddTwoNumbers code05AddTwoNumbers = new Code05_AddTwoNumbers();
        ListNode listNode = code05AddTwoNumbers.addTwoNumbers(l1, l2);
        System.out.println(l1);
        System.out.println(l2);
        System.out.println(listNode);


//        ListNode l = l1;
//        ListNode curL = l;
//        curL.val = 2;
//        System.out.println(l1 + ", " + l1.val);
//        System.out.println(l + ", " + l.val);
//        System.out.println(curL + ", " + curL.val);
    }
}
